#include "sort.h"

static void merge_arr(int *arr, int start, int mid, int end);
static void sort1(int *arr, int start, int end);

void sort(int *arr, int len)
{
    sort1(arr, 0, len - 1);
}

static void sort1(int *arr, int start, int end)
{
    if (start >= end)
    {
        return;
    }
    int mid = (start + end) / 2;
    sort1(arr, start, mid);
    sort1(arr, mid + 1, end);
    merge_arr(arr, start, mid, end);
}

static void merge_arr(int *arr, int start, int mid, int end)
{
    int buf[end - start + 1];
    //需要注意k的下标是从0开始
    int i = start, j = mid + 1, k = 0;
    while (i <= mid && j <= end )
    {
        if (arr[i] <= arr[j])
        {
            buf[k++] = arr[i++];
        }
        else
        {
            buf[k++] = arr[j++];
        }
    }
    while (i <= mid)
    {
        buf[k++] = arr[i++];
    }
    while (j <= end)
    {
        buf[k++] = arr[j++];
    }
    for (int i = 0; i< end - start + 1; i++)
    {
        arr[start + i] = buf[i];
    }
}